// https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 自底向上归并排序链表
// 2. 按size=1,2,4,8...分段进行归并
// 3. cut函数切分指定长度的子链表
// 4. merge函数合并两个有序链表
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "LinkedListUtils.h"

class Solution 
{
public:
    ListNode* sortList(ListNode* head) 
    {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        ListNode* p = head;
        int length = 0;
        while (p != nullptr)
        {
            length++;
            p = p->next;
        }

        for (int size = 1 ; size < length ; size <<= 1)
        {
            ListNode* tail = dummy;
            ListNode* cur = dummy->next;
            
            while (cur != nullptr)
            {
                ListNode* left = cur;
                ListNode* right = cut(left, size);
                cur = cut(right, size);
                tail->next = merge(left, right);

                while (tail->next)
                {
                    tail = tail->next;
                }
            }
        }

        ListNode* ret = dummy->next;
        delete dummy;

        return ret;
    }

    ListNode* cut(ListNode* head, int n)
    {
        ListNode* p = head;
        while (--n && p)
        {
            p = p->next;
        }

        if (p == nullptr)
        {
            return nullptr;
        }

        ListNode* next = p->next;
        p->next = nullptr;

        return next;
    }

    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p->next = l1;
                p = p->next;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                p = p->next;
                l2 = l2->next;
            }
        }

        if (l1)  p->next = l1;
        if (l2)  p->next = l2;

        ListNode* ret = dummy->next;
        delete dummy;

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {4,2,1,3}, nums2 = {-1,5,3,4,0};
    Solution sol;

    ListNode* l1 = createLinkedList(nums1);
    ListNode* l2 = createLinkedList(nums2);

    auto r1 = sol.sortList(l1);
    auto r2 = sol.sortList(l2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}